/*
 * @lc app=leetcode.cn id=338 lang=typescript
 *
 * [338] 比特位计数
 */

// @lc code=start

//  思想：动态规划
//  最低有效位，当前数 i 是否+1可以看最低位是否加一
//  找到第 [i/2]位，奇数+1 偶数不加，通过 &1 实现取余
//  参考：https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/

//  复杂度：O(n)  O(1)

function countBits(n: number): number[] {
    let res = new Array(n + 1).fill(0)
    for (let i = 1; i <= n; i++) {
        res[i] = res[i >> 1] + (i & 1)

    }
    return res
};
// @lc code=end

console.log(countBits(5));
